.

iT邦幫忙

2024 iThome 鐵人賽

DAY 8
0
自我挑戰組

LeetCode 自我修煉馬拉松系列 第 8

Day8: Easy 15-16

  • 分享至 

  • xImage
  •  

今天的題單:

  • Ransom Note

  • Climbing Stairs

383. Ransom Note

判斷 magazine 字串內的字母能不能拼出 ransomNote 字串。

思路:個別紀錄 magazineransomNote 中每個字母的出現次數,再看 ransomNote 的字母在 magazine 中足不足夠。

實作一:用 map

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // map (sorted)
        map<char, int> map_R;
        map<char, int> map_M;

        for (int i = 0; i < ransomNote.length(); i++) {
            if (map_R.find(ransomNote[i]) == map_R.end()) {
                map_R[ransomNote[i]] = 1;
            } else {
                map_R[ransomNote[i]]++;
            }
        }

        for (int i = 0; i < magazine.length(); i++) {
            if (map_M.find(magazine[i]) == map_M.end()) {
                map_M[magazine[i]] = 1;
            } else {
                map_M[magazine[i]]++;
            }
        }
        
        map<char, int>::iterator it_R;

        for (it_R = map_R.begin(); it_R != map_R.end(); it_R++) {
            if (map_M.find(it_R->first) == map_M.end()) { // not found
                return false;
            }

            if (map_R[it_R->first] > map_M[it_R->first]) { // not enough
                return false;
            }
        }
        return true;
    }
};

實作二:題目說字母只有 lowercase letter,可以用改用固定長度 array 紀錄字母次數

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // array
        vector<int> vec_R(26, 0);
        vector<int> vec_M(26, 0);

        for (int i = 0; i < ransomNote.length(); i++) {
            vec_R[ransomNote[i] % 26]++;
        }

        for (int i = 0; i < magazine.length(); i++) {
            vec_M[magazine[i] % 26]++;
        }

        for (int i = 0; i < vec_R.size(); i++) {
            if (vec_M[i] < vec_R[i])
                return false;
        }
        return true;

    }
};

優化:可以只紀錄 magazine 的字母個數,之後 loop ransomNote 時減去相應字母的數量,如果不夠減,或是字母沒出出現,就表示不夠組成。

  • 可以省去 ransomNote 的字母數量表和一個 loop

  • 也可以使用 Unordered_map (Leetcode sample code),查找也是 O(1)。不過以這題的限制,用 array 應該最簡單。

// Leetcode sample code
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
       unordered_map<char, int> charCount;

        for(char c: magazine){
            charCount[c]++;
        }
        for(char c: ransomNote){
            if(charCount[c] == 0){
                return false;
            }
            charCount[c]--;
        }
        return true;
    }
};

70. Climbing Stairs

經典爬樓梯題。一次只能爬一格或兩格,計算爬到第 n 層有幾種爬法。

這題可以觀察一下前幾層的爬法:爬到第 n 層需要 T(n) 種爬法

  • 第一層:只有 1 一種走法 → T(1) = 1

  • 第二層:可以走 1+1 或 2 → T(2) = 2

  • 第三層:可以從第一層走 2 步或從第二層走 1 步 → T(3) = T(1) + T(2) = 3

之後以此類推,得到一個遞迴式:T(n) = T(n-1) + T(n-2),正是 fibonacci 數列。

實作一:使用 recursion,結果 TLE

class Solution {
public:
    int climbStairs(int n) {
        // fibonacci
        return fib(n);
    }

    int fib(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        return fib(n-1) + fib(n-2);
    }
};

實作二:改成 iterative 作法

class Solution {
public:
    int climbStairs(int n) {
        vector<int> fib(60, 0);
        
        fib[0] = 1;
        fib[1] = 1;
        fib[2] = 2;

        for (int i = 3; i <= n; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        return fib[n];
    }
};

上一篇
Day7: Easy 13-14
下一篇
Day9: Easy 17-18
系列文
LeetCode 自我修煉馬拉松30
.
圖片
  直播研討會

尚未有邦友留言

立即登入留言